package org.rowan.adi.linearalgebra;

import java.util.LinkedList;
import org.rowan.adi.Vector;
import org.rowan.adi.components.comp2d.Circle;
import org.rowan.adi.components.comp2d.Component2D;
import org.rowan.adi.components.comp2d.LineSegment2D;
import org.rowan.adi.components.comp2d.Point2D;
import org.rowan.adi.components.comp2d.polygon.IrregularConvexPolygon;
import org.rowan.adi.components.comp2d.polygon.Polygon;
import org.rowan.adi.components.comp2d.polygon.Rectangle;

/**
 * <p>The LinearAlgebra2D class provides collision detection functionality in two
 * dimensional space. This class povides the following specific functionality:
 * The distance between two 2D Components, the cross-sectional area of two 2D
 * Components, whether a moving 2D Component will intersect a stationary 2D
 * Component in a given amount of time, and whether one 2D Component wholly
 * contains another 2D Component.<p>
 *
 * <p>Containment is defined as:
 * <ul><li>Each point of the child component is inside the parent component.</li>
 * <li>A point is inside its parent if the point is in the interior or lies on one of
 * the vertices or edges of the parent.</li></ul></p>
 *
 * <p>Mininum distance is defined as:
 * <ul><li>The shortest distance between any point within the first component
 * to any point within the second component.</li>
 * <li>The points chosen for the mininum distance must be a vertice or a point
 * that lies on an edge.</li>
 * <li>If one of the components contains the either, the distance is zero.</li>
 * <li>If the components intersect, the distance is zero.</li></ul</p>
 *
 * @author Nick Avignone, Michael Liguori, Robert Russell
 * @version 1.0
 */
public class LinearAlgebra2D {

    /**
     * Determines whether the child Component2D is wholly contained by the parent Component2D.
     * @param parent the parent Component2D.
     * @param child the child Component2D.
     * @return <code>true</code> if the child Component2D is wholly contained
     * by the parent Component2D; <code>false</code> otherwise.
     * @throws IllegalArgumentException the arguments are not valid.
     */
    public static boolean contains(Component2D parent, Component2D child) {

        // The parent object is a Circle, so determine which situation to invoke
        if (parent instanceof Circle) {
            if (child instanceof Point2D) {
                return containsCirclePoint((Circle) parent, (Point2D) child);
            }
            if (child instanceof LineSegment2D) {
                return containsCircleLine((Circle) parent, (LineSegment2D) child);
            }
            if (child instanceof Circle) {
                return containsCircleCircle((Circle) parent, (Circle) child);
            }
            if (child instanceof Polygon) {
                return containsCirclePolygon((Circle) parent, (Polygon) child);
            }
        }

        //The parent is a Polygon, so determine which situation to invoke
        if (parent instanceof Polygon) {
            if (child instanceof Point2D) {
                return containsPolygonPoint((Polygon) parent, (Point2D) child);
            }
            if (child instanceof LineSegment2D) {
                return containsPolygonLine((Polygon) parent, (LineSegment2D) child);
            }
            if (child instanceof Polygon) {
                return containsPolygonPolygon((Polygon) parent, (Polygon) child);
            }
            if (child instanceof Circle) {
                return containsPolygonCircle((Polygon) parent, (Circle) child);
            }
        }

        // The parent is a Line Segment, so determine which situation to invoke
        if (parent instanceof LineSegment2D) {
            if (child instanceof Point2D) {
                return containsLinePoint((LineSegment2D) parent, (Point2D) child);
            }
            if (child instanceof LineSegment2D) {
                return containsLineLine((LineSegment2D) parent, (LineSegment2D) child);
            }
        }

        // The parent is a Point, so determine which situation to invoke
        if (parent instanceof Point2D) {
            if (child instanceof Point2D) {
                return containsPointPoint((Point2D) parent, (Point2D) child);
            }
        }

        throw new IllegalArgumentException("The arguments passed to contains is not a valid combination.");
    }

    /**
     * Determines whether the child Circle is wholly contained by the parent Circle.
     * @param circle1 the parent Circle.
     * @param circle2 the child Circle.
     * @return <code>true</code> if the child Circle is wholly contained by the
     * parent Circle; <code>false</code> otherwise.
     */
    private static boolean containsCircleCircle(Circle circle1, Circle circle2) {
        double x1 = circle1.getLocation().getX();
        double y1 = circle1.getLocation().getY();
        double x2 = circle2.getLocation().getX();
        double y2 = circle2.getLocation().getY();

        double distance = Math.sqrt(Math.pow((x2 - x1), 2) + Math.pow((y2 - y1), 2)) + circle2.getRadius();

        if (distance <= circle1.getRadius()) {
            return true;
        } else {
            return false;
        }
    }

    /**
     * Determines whether the child LineSegment2D is wholly contained by the parent Circle.
     * @param circle the parent Circle.
     * @param line the child LineSegment2D.
     * @return <code>true</code> if the child LineSegment2D is wholly contained
     * by the parent Circle; <code>false</code> otherwise.
     */
    private static boolean containsCircleLine(Circle circle, LineSegment2D line1) {
        LinkedList<Point2D> line = line1.getListofPoints();

        if (containsCirclePoint(circle, line.get(0)) && containsCirclePoint(circle, line.get(1))) {
            return true;
        }

        return false;
    }

    /**
     * Determines whether the child Point2D is wholly contained by the parent Circle.
     * @param circle the parent Circle.
     * @param point the child Point2D.
     * @return <code>true</code> if the child Point2D is wholly contained by the
     * parent Circle; <code>false</code> otherwise.
     */
    private static boolean containsCirclePoint(Circle circle, Point2D point) {
        double distance = Math.sqrt(Math.pow((point.getX() - circle.getLocation().getX()), 2) +
                Math.pow((point.getY() - circle.getLocation().getY()), 2));

        if (distance <= circle.getRadius()) {
            return true;
        } else {
            return false;
        }
    }

    /**
     * Determines whether the child Polygon is wholly contained by the parent Circle.
     * @param circle the parent Circle.
     * @param poly the child Polygon.
     * @return <code>true</code> if the child Polygon is wholly contained by the
     * parent Circle; <code>false</code> otherwise.
     */
    private static boolean containsCirclePolygon(Circle circle, Polygon poly) {
        LinkedList<Point2D> componentPoints = poly.getListofPoints();

        for (int i = 0; i < componentPoints.size(); i++) {
            Point2D point = componentPoints.get(i);
            double distance = Math.sqrt(Math.pow((point.getX() - circle.getLocation().getX()), 2) +
                    Math.pow((point.getY() - circle.getLocation().getY()), 2));

            if (distance > circle.getRadius()) {
                return false;
            }
        }

        return true;
    }

    /**
     * Determines whether the child LineSegment2D is wholly contained by the parent LineSegment2D.
     * @param line1 the parent LineSegment2D.
     * @param line2 the child LineSegment2D.
     * @return <code>true</code> if the child LineSegment2D is wholly contained
     * by the parent LineSegment2D; <code>false</code> otherwise.
     */
    private static boolean containsLineLine(LineSegment2D line1, LineSegment2D line2) {

        LinkedList<Point2D> line = line2.getListofPoints();
        if (containsLinePoint(line1, line.get(0)) && containsLinePoint(line1, line.get(1))) {
            return true;
        }
        return false;
    }

    /**
     * Determines whether the child Point2D is wholly contained by the parent LineSegment2D.
     * @param line the parent LineSegment2D.
     * @param point the child Point2D.
     * @return <code>true</code> if the child Point2D is wholly contained by the
     * parent LineSegment2D; <code>false</code> otherwise.
     */
    private static boolean containsLinePoint(LineSegment2D line1, Point2D point) {
        double pointX = point.getX();
        double pointY = point.getY();
        LinkedList<Point2D> line = line1.getListofPoints();
        double linePoint1X = line.get(0).getX();
        double linePoint2X = line.get(1).getX();
        double linePoint1Y = line.get(0).getY();
        double linePoint2Y = line.get(1).getY();

        if ((pointX == linePoint1X && pointY == linePoint1Y) || (pointX == linePoint2X && pointY == linePoint2Y)) {
            return true;
        }

        if ((pointX >= linePoint1X && pointX <= linePoint2X) || (pointX <= linePoint1X && pointX >= linePoint2X)) {
            if ((pointY >= linePoint1Y && pointY <= linePoint2Y) || (pointY <= linePoint1Y && pointY >= linePoint2Y)) {
                double a = (pointY - linePoint1Y) / (pointX - linePoint1X);
                double b = (linePoint2Y - linePoint1Y) / (linePoint2X - linePoint1X);
                if (a == b) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * Determines whether the child Point2D is wholly contained by the parent Point2D.
     * @param point1 the parent Point2D.
     * @param point2 the child Point2D.
     * @return <code>true</code> if the child Point2D is wholly contained by the
     * parent Point2D; <code>false</code> otherwise.
     */
    private static boolean containsPointPoint(Point2D point1, Point2D point2) {
        if ((point1.getX() == point2.getX()) && (point1.getY() == point2.getY())) {
            return true;
        }
        return false;
    }

    /**
     * Determines whether the child Circle is wholly contained by the parent Polygon.
     * @param poly the parent Polygon.
     * @param line the child Circle.
     * @return <code>true</code> if the child Circle is wholly contained
     * by the parent Polygon; <code>false</code> otherwise.
     */
    private static boolean containsPolygonCircle(Polygon poly, Circle circle) {
        if (containsPolygonPoint(poly, new Point2D(circle.getLocation()))) {
            LinkedList<Point2D> point = new LinkedList<Point2D>();
            point.add(new Point2D(circle.getLocation()));
            if (distanceMutual(poly.getListofPoints(), point) >= circle.getRadius()) {
                return true;
            }
        }
        return false;
    }

    /**
     * Determines whether the child LineSegment2D is wholly contained by the parent Polygon.
     * @param poly the parent Polygon.
     * @param line the child LineSegment2D.
     * @return <code>true</code> if the child LineSegment2D is wholly contained
     * by the parent Polygon; <code>false</code> otherwise.
     */
    private static boolean containsPolygonLine(Polygon poly, LineSegment2D line) {
        LinkedList<Point2D> childPoints = line.getListofPoints();

        for (Point2D point : childPoints) {
            if (containsPolygonPoint(poly, point) == false) {
                return false;
            }
        }
        return true;
    }

    /**
     * Determines whether the child Point2D is wholly contained by the parent Polygon.
     * @param circle the parent Polygon.
     * @param poly the child Point2D.
     * @return <code>true</code> if the child Point2D is wholly contained by the
     * parent Polygon; <code>false</code> otherwise.
     */
    private static boolean containsPolygonPoint(Polygon poly, Point2D point) {
        //first make a slop of 0 , horizonal line with the point

        int crossings = 0;
        for (int i = 0; i < poly.getListofPoints().size(); i++) {
            int j = i + 1;
            if (j == poly.getListofPoints().size()) {
                j = 0;
            }
            if (containsLinePoint(new LineSegment2D(poly.getListofPoints().get(i), poly.getListofPoints().get(j)), point)) {
                return true;
            }
            Point2D next = poly.getListofPoints().get(j);
            Point2D current = poly.getListofPoints().get(i);
            double slope = (next.getX() - current.getX()) / (next.getY() - current.getY());
            boolean cond1 = (current.getY() <= point.getY()) && (point.getY() < next.getY());
            boolean cond2 = (next.getY() <= point.getY()) && (point.getY() < current.getY());
            boolean cond3 = point.getX() < slope * (point.getY() - current.getY()) + current.getX();
            if ((cond1 || cond2) && cond3) {
                crossings++;
            }
        }
        return (crossings % 2 != 0);
    }

    /**
     * Determines whether the child Polygon is wholly contained by the parent Polygon.
     * @param parent the parent Polygon.
     * @param child the child Polygon.
     * @return <code>true</code> if the child Polygon is wholly contained by the
     * parent Polygon; <code>false</code> otherwise.
     */
    private static boolean containsPolygonPolygon(Polygon parent, Polygon child) {
        LinkedList<Point2D> childPoints = child.getListofPoints();

        for (Point2D point : childPoints) {
            if (containsPolygonPoint(parent, point) == false) {
                return false;
            }
        }
        return true;
    }

    /**
     * Computes the closest distance between the two Component2D instances given.
     * @param comp1 an instance of Component2D
     * @param comp2 an instance of Componet2D.
     * @return the closest distance between the two Point2D instances given.
     * @throws new IllegalArgumentException the arguments are not valid.
     */
    public static double distance(Component2D comp1, Component2D comp2) {

        // The first parameter is a Polygon, so determine which situation to invoke
        if (comp1 instanceof Polygon) {
            if (comp2 instanceof Polygon) {
                return distancePolygonPolygon((Polygon) comp1, (Polygon) comp2);
            }
            if (comp2 instanceof LineSegment2D) {
                return distanceLinePolygon((LineSegment2D) comp2, (Polygon) comp1);
            }
            if (comp2 instanceof Point2D) {
                return distancePolygonPoint((Polygon) comp1, (Point2D) comp2);
            }
            if (comp2 instanceof Circle) {
                return distancePolygonCircle((Polygon) comp1, (Circle) comp2);
            }
        }

        // The second parameter is a Polygon, so determine which situation to invoke
        if (comp2 instanceof Polygon) {
            if (comp1 instanceof Polygon) {
                return distancePolygonPolygon((Polygon) comp2, (Polygon) comp1);
            }
            if (comp1 instanceof LineSegment2D) {
                return distanceLinePolygon((LineSegment2D) comp1, (Polygon) comp2);
            }
            if (comp1 instanceof Point2D) {
                return distancePolygonPoint((Polygon) comp2, (Point2D) comp1);
            }
            if (comp1 instanceof Circle) {
                return distancePolygonCircle((Polygon) comp2, (Circle) comp1);
            }
        }

        // The first parameter is a Circle, so determine which situation to invoke
        if (comp1 instanceof Circle) {
            if (comp2 instanceof Polygon) {
                return distancePolygonCircle((Polygon) comp2, (Circle) comp1);
            }
            if (comp2 instanceof Circle) {
                return distanceCircleCircle((Circle) comp1, (Circle) comp2);
            }
            if (comp2 instanceof Point2D) {
                return distanceCirclePoint((Circle) comp1, (Point2D) comp2);
            }
            if (comp2 instanceof LineSegment2D) {
                return distanceCircleLine((Circle) comp1, (LineSegment2D) comp2);
            }
        }

        // The second parameter is a Circle, so determine which situation to invoke
        if (comp2 instanceof Circle) {
            if (comp1 instanceof Polygon) {
                return distancePolygonCircle((Polygon) comp1, (Circle) comp2);
            }
            if (comp1 instanceof Circle) {
                return distanceCircleCircle((Circle) comp2, (Circle) comp1);
            }
            if (comp1 instanceof Point2D) {
                return distanceCirclePoint((Circle) comp2, (Point2D) comp1);
            }
            if (comp1 instanceof LineSegment2D) {
                return distanceCircleLine((Circle) comp2, (LineSegment2D) comp1);
            }
        }

        // The first parameter is a Line Segment, so determine which situation to invoke
        if (comp1 instanceof LineSegment2D) {
            if (comp2 instanceof Polygon) {
                return distanceLinePolygon((LineSegment2D) comp1, (Polygon) comp2);
            }
            if (comp2 instanceof Circle) {
                return distanceCircleLine((Circle) comp2, (LineSegment2D) comp1);
            }
            if (comp2 instanceof Point2D) {
                return distancePointLine((Point2D) comp2, (LineSegment2D) comp1);
            }
            if (comp2 instanceof LineSegment2D) {
                return distanceLineLine((LineSegment2D) comp2, (LineSegment2D) comp1);
            }
        }

        // The second parameter is a Line Segment, so determine which situation to invoke
        if (comp2 instanceof LineSegment2D) {
            if (comp1 instanceof Polygon) {
                return distanceLinePolygon((LineSegment2D) comp2, (Polygon) comp1);
            }
            if (comp1 instanceof Circle) {
                return distanceCircleLine((Circle) comp1, (LineSegment2D) comp2);
            }
            if (comp1 instanceof Point2D) {
                return distancePointLine((Point2D) comp1, (LineSegment2D) comp2);
            }
            if (comp1 instanceof LineSegment2D) {
                return distanceLineLine((LineSegment2D) comp1, (LineSegment2D) comp2);
            }
        }

        // The first parameter is a Point, so determine which situation to invoke
        if (comp1 instanceof Point2D) {
            if (comp2 instanceof Polygon) {
                return distancePolygonPoint((Polygon) comp2, (Point2D) comp1);
            }
            if (comp2 instanceof Circle) {
                return distanceCirclePoint((Circle) comp2, (Point2D) comp1);
            }
            if (comp2 instanceof Point2D) {
                return distancePointPoint((Point2D) comp1, (Point2D) comp2);
            }
            if (comp2 instanceof LineSegment2D) {
                return distancePointLine((Point2D) comp1, (LineSegment2D) comp2);
            }
        }

        // The second parameter is a Point, so determine which situation to invoke
        if (comp2 instanceof Point2D) {
            if (comp1 instanceof Polygon) {
                return distancePolygonPoint((Polygon) comp2, (Point2D) comp2);
            }
            if (comp1 instanceof Circle) {
                return distanceCirclePoint((Circle) comp1, (Point2D) comp2);
            }
            if (comp1 instanceof Point2D) {
                return distancePointPoint((Point2D) comp2, (Point2D) comp1);
            }
            if (comp1 instanceof LineSegment2D) {
                return distancePointLine((Point2D) comp2, (LineSegment2D) comp1);
            }
        }

        throw new IllegalArgumentException("The arguments passed to this method are not valid.");
    }

    /**
     * Computes the closest distance between the two Circle instances given.
     * @param circle1 an instance of Circle.
     * @param circle2 an instance of Circle.
     * @return the closest distance between the two Circle instances given.
     */
    private static double distanceCircleCircle(Circle circle1, Circle circle2) {
        Point2D point1 = new Point2D(circle1.getLocation());
        Point2D point2 = new Point2D(circle2.getLocation());
        double distance = Math.sqrt(Math.pow((point2.getX() - point1.getX()), 2) + Math.pow((point2.getY() - point1.getY()), 2));
        return distance - circle1.getRadius() - circle2.getRadius();
    }

    /**
     * Computes the closest distance between the LineSegment2D and Circle instances given.
     * @param circle an instance of Circle.
     * @param line an instance of LineSegment2D.
     * @return the closest distance between the LineSegment2D and Circle instances given.
     */
    private static double distanceCircleLine(Circle circle, LineSegment2D line) {
        return distancePointLine(new Point2D(circle.getLocation()), line) - circle.getRadius();
    }

    /**
     * Computes the closest distance between the Point2D and Circle instances given.
     * @param circle1 an instance of Circle.
     * @param point1 an instance of Point2D.
     * @return the closest distance between the Point2D and Circle instances given.
     */
    private static double distanceCirclePoint(Circle circle, Point2D point) {
        if (contains(circle, point)) {
            return 0.0;
        }

        Point2D circlePoint = new Point2D(circle.getLocation());

        double distance = Math.sqrt(Math.pow((point.getX() - circlePoint.getX()), 2) +
                Math.pow((point.getY() - circlePoint.getY()), 2));

        return distance - circle.getRadius();
    }

    /**
     * Computes the closest distance between the two LineSegment2D instances given.
     * @param line1 an instance of LineSegment2D.
     * @param line2 an instance of LineSegment2D.
     * @return the closest distance between the two LineSegment2D instances given.
     */
    private static double distanceLineLine(LineSegment2D line1, LineSegment2D line2) {
        return distanceMutual(line1.getListofPoints(), line2.getListofPoints());
    }

    /**
     * Computes the closest distance between the LineSegment2D and Polygon instances given.
     * @param poly an instance of Polygon.
     * @param line an instance of LineSegment2D.
     * @return the closest distance between the LineSegment2D and Polygon
     * instances given.
     */
    private static double distanceLinePolygon(LineSegment2D line, Polygon poly) {
        return distanceMutual(line.getListofPoints(), poly.getListofPoints());
    }

    /**
     * Computes the closest distance between the Point2D and LineSegment instances given.
     * @param line an instance of LineSegment2D.
     * @param point an instance of Point2D.
     * @return the closest distance between the Point2D and LineSegment instances given.
     */
    private static double distancePointLine(Point2D point, LineSegment2D line) {
        // http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/
        Point2D linePoint1 = line.getListofPoints().get(0);
        Point2D linePoint2 = line.getListofPoints().get(1);

        double xDelta = linePoint2.getX() - linePoint1.getX();
        double yDelta = linePoint2.getY() - linePoint1.getY();

        double u = ((point.getX() - linePoint1.getX()) * xDelta + (point.getY() - linePoint1.getY()) * yDelta) / (xDelta * xDelta + yDelta * yDelta);

        Point2D closest;
        if (u < 0) {
            closest = linePoint1;
        } else if (u > 1) {
            closest = linePoint2;
        } else {
            closest = new Point2D(new Vector(linePoint1.getX() + u * xDelta, linePoint1.getY() + u * yDelta));
        }

        return distance(closest, point);
    }

    /**
     * Computes the closest distance between the two Point2D instances given.
     * @param point1 an instance of Point2D.
     * @param point2 an instance of Point2D.
     * @return the closest distance between the two Point2D instances given.
     */
    private static double distancePointPoint(Point2D point1, Point2D point2) {
        return Math.sqrt(Math.pow((point2.getX() - point1.getX()), 2) +
                Math.pow((point2.getY() - point1.getY()), 2));
    }

    /**
     * Computes the closest distance between a the Circle and Polygon instances given.
     * @param poly an instance of Polygon.
     * @param circle an instance of Circle.
     * @return the closest distance between the Circle and Polygon instances given.
     */
    private static double distancePolygonCircle(Polygon poly, Circle circle) {
        return distancePolygonPoint(poly, new Point2D(circle.getLocation()));
    }

    /**
     * Computes the closest distance between a the Point2D and Polygon instances given.
     * @param poly an instance of Polygon.
     * @param point an instance of Point2D.
     * @return the closest distance between the Point2D and Polygon instances given.
     */
    private static double distancePolygonPoint(Polygon poly, Point2D point) {
        // Base case, if the polygon contains the point, then there is no distance
        if (contains(poly, point)) {
            return 0.0;
        }

        LinkedList<Point2D> compPts = poly.getListofPoints();
        int compSize = compPts.size();
        double shortest = Double.MAX_VALUE;
        double temp;
        double[] cX = new double[compSize];
        double[] cY = new double[compSize];
        double x1 = point.getX();
        double y1 = point.getY();

        // puts all the parent and childs x and y points into seperate lists
        // (easier to read code and write purposes)
        for (int i = 0; i < compSize; i++) {
            cX[i] = compPts.get(i).getX();
            cY[i] = compPts.get(i).getY();
        }

        for (int i = 0; i < compSize; i++) {
            temp = distancePointLine(new Point2D(new Vector(x1, y1)), new LineSegment2D(new Point2D(new Vector(cX[i], cY[i])),
                    new Point2D(new Vector(cX[(i + 1) % compSize], cY[(i + 1) % compSize]))));
            if (temp < shortest) {
                shortest = temp;
            }
        }
        return shortest;
    }

    /**
     * Determines the shortest distance between the two lists of points given.
     * @param list1 a list of points.
     * @param list2 a list of points.
     * @return the shortesrt distance between the two lists of points given.
     */
    private static double distanceMutual(LinkedList<Point2D> list1, LinkedList<Point2D> list2) {
        int comp1Size = list1.size();
        int comp2Size = list2.size();
        double[] c1X = new double[comp1Size + 1];
        double[] c1Y = new double[comp1Size + 1];
        double[] c2X = new double[comp2Size + 1];
        double[] c2Y = new double[comp2Size + 1];

        // puts all the parent and childs x and y points into seperate lists
        // (easier to read code and write purposes)
        for (int i = 0; i < comp1Size; i++) {
            c1X[i] = list1.get(i).getX();
            c1Y[i] = list1.get(i).getY();
        }
        for (int i = 0; i < comp2Size; i++) {
            c2X[i] = list2.get(i).getX();
            c2Y[i] = list2.get(i).getY();
        }
        double shortest = Double.MAX_VALUE;
        double temp;
        /*
         * finds the two vertices with the shortest distance from each other
         * and assigns them, si, sj
         */
        for (int j = 0; j < comp2Size; j++) {
            for (int i = 0; i < comp1Size; i++) {
                temp = distancePointLine(new Point2D(new Vector(c2X[j], c2Y[j])), new LineSegment2D(new Point2D(new Vector(c1X[i], c1Y[i])),
                        new Point2D(new Vector(c1X[(i + 1) % comp1Size], c1Y[(i + 1) % comp1Size]))));
                if (temp < shortest) {
                    shortest = temp;
                }
            }
        }

        for (int j = 0; j < comp1Size; j++) {
            for (int i = 0; i < comp2Size; i++) {
                temp = distancePointLine(new Point2D(new Vector(c1X[j], c1Y[j])), new LineSegment2D(new Point2D(new Vector(c2X[i], c2Y[i])),
                        new Point2D(new Vector(c2X[(i + 1) % comp2Size], c2Y[(i + 1) % comp2Size]))));
                if (temp < shortest) {
                    shortest = temp;
                }
            }
        }
        return shortest;

    }

    /**
     * Computes the closest distance between the two Polygon instances given.
     * @param poly1 an instance of Polygon.
     * @param poly2 an instance of Polygon.
     * @return the closest distance between the two Polygon instances given.
     */
    private static double distancePolygonPolygon(Polygon poly1, Polygon poly2) {
        LinkedList<Point2D> poly1Pts = poly1.getListofPoints();
        LinkedList<Point2D> poly2Pts = poly2.getListofPoints();
        return distanceMutual(poly1Pts, poly2Pts);
    }

        //=========INTERSECT METHODS=============

    /**
     * Determines whether the moving Component2D will intersect the boundary
     * Component2D in a given amount of time.
     * @param moving an instance of Component2D which has a non-zero trajectory.
     * @param boundary  an instance of Component2D which represents the potential
     * point of intersection. This boundary is stationary.
     * @param time the the maximum amount of time given for the Component2D
     * instances to intersect.
     * @return <code>true</code> if the moving Component2D will intersect the
     * boundary Component2D in a given amount of time; <code>false</code> otherwise.
     * @throws IllegalArgumentException the boundary cannot be moving.
     */
    public static boolean intersect(Component2D moving, Component2D boundary, double time) {
        if (boundary.getTrajectory() != null) {
            throw new IllegalArgumentException("Boundary Cannot be moving");
        }
        if (moving.getTrajectory() == null) {
            throw new IllegalArgumentException("Must have a Vector");
        }

        boolean intersect = false;
        Vector trajectory = moving.getTrajectory();
        double vectorMagnitude = trajectory.magnitude();
        double vectorOverTime = vectorMagnitude * time;
        double distanceBetween = distance(moving, boundary);
        double movingObjectOrignalX = moving.getLocation().getX();
        double movingObjectOrignalY = moving.getLocation().getY();
        //If there is a trajectory we continue
        if (!trajectory.isZeroVector()) {
            // see if the magnitude and given time can reach the object
            if (vectorOverTime >= distanceBetween) {
                //determine the possible time of intersection.
                double timeOfPossibleIntersection = distanceBetween / trajectory.magnitude();
                //with new given time, comput the new vector distance
                Vector vectorByDistance = trajectory.multiply(timeOfPossibleIntersection);

                //move the object to its new location, see if they intersect
                //need deep copy method possibly.
                moving.setLocation(new Vector(movingObjectOrignalX + vectorByDistance.getX(), movingObjectOrignalY + vectorByDistance.getY()));
                if (moving instanceof Circle) {
                    if (intersectArea((Circle) moving, boundary) != 0 || contains(moving, boundary)) {
                        intersect = true;
                    }

                } else if (boundary instanceof Circle) {
                    if (intersectArea((Circle) boundary, moving) != 0 || contains(moving, boundary)) {
                        intersect = true;
                    }

                } else {
                    if (intersect(moving, boundary) != null || contains(moving, boundary)) {
                        intersect = true;
                    }
                }
            }
        } else {
            //Not moving. Check if they are currently intersecting?
            if (moving instanceof Circle) {
                if (intersectArea((Circle) moving, boundary) != 0 || contains(moving, boundary)) {
                    intersect = true;
                }

            } else if (boundary instanceof Circle) {
                if (intersectArea((Circle) boundary, moving) != 0 || contains(moving, boundary)) {
                    intersect = true;
                }

            } else {
                if (intersect(moving, boundary) != null || contains(moving, boundary)) {
                    intersect = true;
                }
            }
        }

        //make if we moved it , its back in its original position
        moving.setLocation(new Vector(movingObjectOrignalX, movingObjectOrignalY));
        return intersect;
    }



    /**
     * Computes the cross-sectional area of the two Component2D instances given.
     * @param component1 an instance of Component2D.
     * @param component2 an instance of Component2D.
     * @return an instance of IrregularConvexPolygon, which represents the
     * cross-sectional area of the two Component2D instances given.
     * @throws IllegalArgumentException instances of Circle cannot be passed into
     * this version of intersection because the area returned is not an instance
     * of Component but the actual value of the area. non-polygon objects will
     * be implemented in future releases.
     */
    public static Component2D intersect(Component2D component1, Component2D component2) {
        // The first parameter is a Point, so determine which situation to invoke
        if (component1 instanceof Point2D) {
            if (component2 instanceof Point2D) {
                return intersectPointPoint((Point2D) component1, (Point2D) component2);
            }

            if (component2 instanceof LineSegment2D) {
                return intersectPointLine((Point2D) component1, (LineSegment2D) component2);
            }

            if (component2 instanceof Polygon) {
                return intersectPointPolygon((Point2D) component1, (Polygon) component2);
            }

            if (component2 instanceof Circle) {
                return intersectCirclePoint((Circle) component2, (Point2D) component1);
            }
        }

        // The first parameter is a Line Segment, so determine which situation to invoke
        if (component1 instanceof LineSegment2D) {
            if (component2 instanceof Point2D) {
                return intersectPointLine((Point2D) component2, (LineSegment2D) component1);
            }

            if (component2 instanceof LineSegment2D) {
                return intersectLineLine((LineSegment2D) component1, (LineSegment2D) component2);
            }

            if (component2 instanceof Polygon) {
                return intersectLinePolygon((LineSegment2D) component1, (Polygon) component2);
            }

            if (component2 instanceof Circle) {
                return intersectCircleLine((Circle) component2, (LineSegment2D) component1);
            }
        }

        // The first parameter is a Polygon, so determine which situation to invoke
        if (component1 instanceof Polygon) {
            if (component2 instanceof Point2D) {
                return intersectPointPolygon((Point2D) component2, (Polygon) component1);
            }

            if (component2 instanceof LineSegment2D) {
                return intersectLinePolygon((LineSegment2D) component2, (Polygon) component1);
            }

            if (component2 instanceof Polygon) {
                return intersectPolygonPolygon((Polygon) component1, (Polygon) component2);
            }

            if (component2 instanceof Circle) {
                throw new IllegalArgumentException("Circles cannot be passed into this version of intersection," +
                        "as the cross-sectional area cannot be returned in the form of a Component2D object." +
                        "Please invoke intersect(Circle circle, Component component) instead.");
            }
        }

        // The first parameter is a Circle, so determine which situation to invoke
        if (component1 instanceof Circle) {
            if (component2 instanceof Point2D) {
                return intersectCirclePoint((Circle) component1, (Point2D) component2);
            }

            if (component2 instanceof LineSegment2D) {
                return intersectCircleLine((Circle) component1, (LineSegment2D) component2);
            }

            if (component2 instanceof Circle || component2 instanceof Polygon) {
                throw new IllegalArgumentException("Circles cannot be passed into this version of intersection," +
                        "as the cross-sectional area cannot be returned in the form of a Component2D object." +
                        "Please invoke intersect(Circle circle, Component component) instead.");
            }
        }

        throw new IllegalArgumentException("The arguments passed to this method are not valid.");
    }

    /**
     * Computes the cross-sectional area of the Circle and Component2D instances given.
     * @param circle1 an instance of Circle.
     * @param circle2 an instance of Component2D
     * @return the cross-sectional area of the Circle and Component2D instances given.
     * @throws IllegalArgumentException instances of Point2D and LineSegment2D cannot be
     * passed into this version of intersect. The cross-sectional area of a point
     * or a line segment with a circle cannot be represented in terms of a double.
     */
    public static double intersectArea(Circle circle, Component2D component) {
        if (component instanceof Circle) {
            return intersectCircleCircle(circle, (Circle) component);
        } else if (component instanceof Polygon) {
            return intersectCirclePolygon(circle, (Polygon) component);
        } else {
            throw new IllegalArgumentException("Point2D and LineSegment2D instances" +
                    "are not allowed to be passed into this version of intersect. Please" +
                    "invoke intersect(Component1, Component2). The cross-sectional area of a " +
                    "point or a line segment with a circle cannot be represented in terms of a double.");
        }
    }

    /**
     * Computes the cross-sectional area of the two Circle instances given.
     * @param circle1 an instance of Circle.
     * @param circle2 an instance of Circle.
     * @return the cross-sectional area of the two Circle instances given.
     */
    private static double intersectCircleCircle(Circle circle1, Circle circle2) {
        //for check to see if they are in range
        //equations from
        //http://local.wasp.uwa.edu.au/~pbourke/geometry/2circle/
        //http://mathworld.wolfram.com/CircularSegment.html
        double circleOneX = circle1.getLocation().getX();
        double circleOneY = circle1.getLocation().getY();
        double circleTwoX = circle2.getLocation().getX();
        double circleTwoY = circle2.getLocation().getY();
        double deltaX = circleTwoX - circleOneX;
        double deltaY = circleTwoY - circleOneY;
        double circleOneRadius = circle1.getRadius();
        double circleTwoRadius = circle2.getRadius();
        double distanceSqr = (deltaX * deltaX) + (deltaY * deltaY);
        double distance = Math.sqrt(distanceSqr);

        if ((distance > (circleOneRadius + circleTwoRadius) ||
                (distance < Math.abs(circleTwoRadius - circleOneRadius)))) {
            return 0.0;
        } else if (containsCircleCircle(circle1, circle2) || containsCircleCircle(circle2, circle1)) {
            //find small one

            double smallerCircleArea;
            if (circleOneRadius < circleTwoRadius) {
                smallerCircleArea = circle1.computeArea();
            } else {
                smallerCircleArea = circle2.computeArea();
            }
            return smallerCircleArea;

        } else {
            //First find two intersecting points
            //general distance a^2 + h^2 = r1^2 and b^2 + h^2 = r2^2
            //solve for a, distance to middlepoint of intersectopm between two circles
            //a = (r1^2 - r2^2 + distance^2)/(2distance)
            double a = (distanceSqr + (circleTwoRadius * circleTwoRadius) - (circleOneRadius * circleOneRadius)) / (2 * distance);
            // now solve for h
            double h = Math.sqrt((circleOneRadius * circleOneRadius) - (a * a));

            //Now calculate the area
            //find theta using rule of cosines
            // cosine = a^2 + b^2 - c^2/2ab
            double theta = Math.acos((2 * Math.pow(circleOneRadius, 2) - Math.pow(2 * h, 2)) / (2 * circleOneRadius * circleOneRadius));
            double area = (circleOneRadius * circleOneRadius) * (theta - Math.sin(theta));
            return area;
        }
    }

    /**
     * Computes the cross-sectional area of the Circle and LineSegment2D instances given.
     * @param circle an instance of Circle.
     * @param line1 an instance of LineSegment2D.
     * @return the cross-sectional area of the Circle and LineSegment2D instances given.
     */
    private static Component2D intersectCircleLine(Circle circle, LineSegment2D line) {
        if (containsCircleLine(circle, line)) {
            return line;
        }

        //http://stackoverflow.com/questions/1073336/circle-line-collision-detection
        double x1 = line.getListofPoints().get(0).getX();
        double x2 = line.getListofPoints().get(1).getX();
        double y1 = line.getListofPoints().get(0).getY();
        double y2 = line.getListofPoints().get(1).getY();
        double circleOriginX = circle.getLocation().getX();
        double circleOriginY = circle.getLocation().getY();
        double circleRadius = circle.getRadius();
        double deltaX = x2 - x1;
        double deltaY = y2 - y1;

        if ((deltaX == 0) && (deltaY == 0)) {
            // A and B are the same points, no way to calculate intersection
            return null;
        }

        double dl = (deltaX * deltaX + deltaY * deltaY);
        double t = ((circleOriginX - x1) * deltaX + (circleOriginY - y1) * deltaY) / dl;

        // point on a line nearest to circle center
        double nearestX = x1 + t * deltaX;
        double nearestY = y1 + t * deltaY;

        double dist = Math.sqrt(Math.pow((nearestX - circleOriginX), 2) + Math.pow((nearestY - circleOriginY), 2));


        if (dist == circleRadius) {
            // line touches circle; one intersection point
            return new Point2D(new Vector(nearestX, nearestY));
        } else if (dist < circleRadius) {
            // two intersection points
            // intersection point nearest to A
            double dt = Math.sqrt(circleRadius * circleRadius - dist * dist) / Math.sqrt(dl);
            double intersectPoint1X = x1 + (t - dt) * deltaX;
            double intersectPoint1Y = y1 + (t - dt) * deltaY;

            // intersection point farthest from A
            double intersectPoint2X = x1 + (t + dt) * deltaX;
            double intersectPoint2Y = y1 + (t + dt) * deltaY;

            Point2D intersectionPoint1 = new Point2D(new Vector(intersectPoint1X, intersectPoint1Y));
            Point2D intersectionPoint2 = new Point2D(new Vector(intersectPoint2X, intersectPoint2Y));

            boolean intersectionPoint1Valid = false;
            boolean intersectionPoint2Valid = false;

            //Check to see if the intersection points is in bounds of the line
            if (containsLinePoint(line, intersectionPoint1)) {
                intersectionPoint1Valid = true;
            }
            if (containsLinePoint(line, intersectionPoint2)) {
                intersectionPoint2Valid = true;
            }

            /*
             * Cases for amount of intersection points
             * If 2, its a line , 1 its a point , 0 theres no intersection
             */
            if (intersectionPoint1Valid && intersectionPoint2Valid) {
                return new LineSegment2D(intersectionPoint1, intersectionPoint2);
            } else if (intersectionPoint1Valid && !intersectionPoint2Valid) {
                return intersectionPoint1;
            } else if (!intersectionPoint1Valid && intersectionPoint2Valid) {
                return intersectionPoint2;
            } else {
                return null;
            }
        } else {
            return null;
        }
    }

    /**
     * Computes the cross-sectional area of the Circle and Point2D instances given.
     * @param circle an instance of Circle.
     * @param line1 an instance of Point2D.
     * @return the cross-sectional area of the Circle and Point2D instances given.
     */
    private static Point2D intersectCirclePoint(Circle circle, Point2D point) {
        if (contains(circle, point)) {
            return point;
        } else {
            return null;
        }
    }

    /**
     * Computes the cross-sectional area of the Circle and Polygon instances given.
     * @param circle an instance of Circle.
     * @param polygon an instance of Polygon.
     * @return the cross-sectional area of the Circle and Polygon instances given.
     */
    private static double intersectCirclePolygon(Circle circle, Polygon polygon) {
        LinkedList<Point2D> points = polygon.getListofPoints();
        LinkedList<Point2D> intersectionShape = new LinkedList<Point2D>();

        if (contains(circle, polygon)) {
            return polygon.computeArea();
        }

        if (contains(polygon, circle)) {
            return circle.computeArea();
        }
        // Maintains a list of indexes of points which are on the perimeter of the circle.
        // List used later on to compute the area of  non-polygon sections.
        LinkedList<Integer> circlePtsIndex = new LinkedList<Integer>();

        for (int i = 0; i < points.size(); i++) {
            Point2D point = points.get(i);

            // Determine if each point in polygon exists within the circle.
            if (LinearAlgebra2D.contains(circle, point)) {
                intersectionShape.add(point);

                // Point does not exist within the circle, but perhaps the line segment
                // which connects this point and the next point intersects the circle.
                // If that is the case, store the points of intersection and make note
                // of these points in the circlePtsIndex list computing the area later.
            }
            Component2D intersection = intersectCircleLine(circle, new LineSegment2D(point, points.get((i + 1) % points.size())));

            if (intersection != null) {
                // Simply just a point so add it to the intersecting shape.
                if (intersection instanceof Point2D) {
                    intersectionShape.add((Point2D) intersection);
                    circlePtsIndex.add(intersectionShape.size() - 1);
                    // This edge intersects the circle twice, so add both points
                    // to the intersecting shape.
                    } else if (intersection instanceof LineSegment2D) {
                    LineSegment2D segment = (LineSegment2D) intersection;
                    intersectionShape.add((Point2D) segment.getListofPoints().get(0));
                    circlePtsIndex.add(intersectionShape.size() - 1);
                    intersectionShape.add((Point2D) segment.getListofPoints().get(1));
                    circlePtsIndex.add(intersectionShape.size() - 1);
                }

            }
        }

        // Compute the polygon area of the intersecting shape. This computations
        // omits the curved non-polygon sections from the calculation.
        IrregularConvexPolygon irregPoly = new IrregularConvexPolygon(intersectionShape);
        double area = irregPoly.computeArea();

        // Go through pairs of points, which lie both on the circle's perimiter and
        // the polygon.
        while (!circlePtsIndex.isEmpty()) {
            int index1 = circlePtsIndex.remove(0).intValue();
            int index2 = circlePtsIndex.remove(0).intValue();

            Point2D point1 = intersectionShape.get(index1);
            Point2D point2 = intersectionShape.get(index2);

            // Determine the angle between the edges P1-Circle Center and P2-Circle Center.
            // Once the angle is found by using the law of cosines, the partial area
            // for this portion of the circle can be found.
            double a = distance(circle.getListofPoints().get(0), point1);
            double b = distance(point1, point2);
            double c = distance(point2, circle.getListofPoints().get(0));

            double theta = Math.acos((Math.pow(a, 2) + Math.pow(c, 2) - Math.pow(b, 2)) / (2 * a * c));

            // Subtract the triangle area from the partial circle area to obtain
            // the non-polygon area that was omited from the polygon area calculation previously.
            double circleSliceArea = 0.5 * Math.pow(circle.getRadius(), 2) * (theta - Math.sin(theta));

            area += (circleSliceArea);
        }

        return area;
    }

    /**
     * Computes the cross-sectional area of the two LineSegment2D instances given.
     * @param line1 an instance of LineSegment2D.
     * @param line2 an instance of LineSegment2D.
     * @return the cross-sectional area of the two LineSegment2D instances given.
     */
    private static Component2D intersectLineLine(LineSegment2D line1, LineSegment2D line2) {

        // Get line 1 points
        double x2 = line1.getListofPoints().get(1).getX();
        double x1 = line1.getListofPoints().get(0).getX();
        double y2 = line1.getListofPoints().get(1).getY();
        double y1 = line1.getListofPoints().get(0).getY();
        boolean line1undefined = false;
        double slopeOfLine1 = 0;
        double yInterseptLine1 = 0;

        // Get line 2 Points
        double x4 = line2.getListofPoints().get(1).getX();
        double x3 = line2.getListofPoints().get(0).getX();
        double y4 = line2.getListofPoints().get(1).getY();
        double y3 = line2.getListofPoints().get(0).getY();
        boolean line2undefined = false;
        double yInterseptLine2 = 0;
        double slopeOfLine2 = 0;

        //Check to see if Line 1 is undefined
        if (x2 - x1 != 0) {
            slopeOfLine1 = (y2 - y1) / (x2 - x1);
            yInterseptLine1 =
                    y1 - slopeOfLine1 * x1;
        } else {
            //Cant divide by zero
            line1undefined = true;
        }

        //Check to see if Line 2 is undefined
        if (x4 - x3 != 0) {
            slopeOfLine2 = (y4 - y3) / (x4 - x3);
            yInterseptLine2 =
                    y3 - slopeOfLine2 * x3;
        } else {
            //Cant divide by zero
            line2undefined = true;
        }

        // both undefined is a special case
        //Check to see if any are undefined to do the right calculation
        if (line1undefined && line2undefined) {

            //A Point of line 2 must be between endpoints of line 1
            //We dont know which one so we check both
            if (x1 == x3) {
                Point2D intersectedPoint1 = null;
                Point2D intersectedPoint2 = null;

                //find out which point of line 1 is in the middle of line 2
                if (((y1 <= y4) && (y1 >= y3)) || ((y1 >= y4) && (y1 <= y3))) {
                    intersectedPoint1 = line1.getListofPoints().get(0);
                } else if (((y2 <= y4) && (y2 >= y3)) || ((y2 >= y4) && (y2 <= y3))) {
                    intersectedPoint1 = line1.getListofPoints().get(1);
                }

                //find out which point of line 2 is in the middle of line 1
                if (((y3 <= y2) && (y3 >= y1)) || ((y3 >= y2) && (y3 <= y1))) {
                    intersectedPoint2 = line2.getListofPoints().get(0);
                } else if (((y4 <= y2) && (y4 >= y1)) || ((y4 >= y2) && (y4 <= y1))) {
                    intersectedPoint2 = line2.getListofPoints().get(1);
                }

                //Have two points to the line segment. Determine if they are the
                //same point. if they are, just return 1 point
                if (intersectedPoint1 != null && intersectedPoint2 != null) {
                    if ((intersectedPoint1.getX() == intersectedPoint2.getX()) &&
                            (intersectedPoint1.getY() == intersectedPoint2.getY())) {
                        return intersectedPoint1;
                    } else {
                        return new LineSegment2D(intersectedPoint1, intersectedPoint2);
                    }

                }
            }
        } else if (!line1undefined && line2undefined) {
            //Line2 to is undefined. Line 1 is Normal
            double intersectYPoint = slopeOfLine1 * x3 + yInterseptLine1;
            if (((x3 <= x2 && x3 >= x1) || (x3 >= x2 && x3 <= x1)) &&
                    ((intersectYPoint <= y4 && intersectYPoint >= y3) ||
                    (intersectYPoint >= y4 && intersectYPoint <= y3))) {
                return new Point2D(new Vector(x3, intersectYPoint));
            }

        } else if (line1undefined && !line2undefined) {
            //Line1 is Undefined, Line 2 is Normal
            double intersectYPoint = slopeOfLine2 * x1 + yInterseptLine2;
            if (((x1 <= x4 && x1 >= x3) || (x1 >= x4 && x1 <= x3)) &&
                    ((intersectYPoint <= y2 && intersectYPoint >= y1) ||
                    (intersectYPoint >= y2 && intersectYPoint <= y1))) {
                return new Point2D(new Vector(x1, intersectYPoint));
            }

        } else if ((slopeOfLine1 == slopeOfLine2) && (yInterseptLine1 == yInterseptLine2)) {
            //They are the same line but we dont know if the lines intersect or not
            if (contains(line1, line2)) {
                return line2;
            }

            if (contains(line2, line1)) {
                return line1;
            }

            Point2D intersectedPoint1 = null;
            Point2D intersectedPoint2 = null;

            //find out which point of line 1 is in the middle of line 2
            if (((x1 <= x4) && (x1 >= x3)) || ((x1 >= x4) && (x1 <= x3))) {
                intersectedPoint1 = line1.getListofPoints().get(0);
            } else if (((x2 <= x4) && (x2 >= x3)) || ((x2 >= x4) && (x2 <= x3))) {
                intersectedPoint1 = line1.getListofPoints().get(1);
            }

            //find out which point of line 2 is in the middle of line 1
            if (((x3 <= x2) && (x3 >= x1)) || ((x3 >= x2) && (x3 <= x1))) {
                intersectedPoint2 = line2.getListofPoints().get(0);
            } else if (((x4 <= x2) && (x4 >= x1)) || ((x4 >= x2) && (x4 <= x1))) {
                intersectedPoint2 = line2.getListofPoints().get(1);
            }

            //Check to see if they intersect at one point or not
            if (intersectedPoint1 != null && intersectedPoint2 != null) {
                if ((intersectedPoint1.getX() == intersectedPoint2.getX()) &&
                        (intersectedPoint1.getY() == intersectedPoint2.getY())) {
                    return intersectedPoint1;
                } else {
                    return new LineSegment2D(intersectedPoint1, intersectedPoint2);
                }

            }
        } else if ((slopeOfLine1 == slopeOfLine2) && (yInterseptLine1 != yInterseptLine2)) {
            //Make sure that the lines arent parallel if they have the same slope.
            return null;

        } else {
            //Finally Basic Line equation, no special cases
            double intersectXPoint = (yInterseptLine2 - yInterseptLine1) / (slopeOfLine1 - slopeOfLine2);
            //plug x back in
            double intersectYPoint = (slopeOfLine1 * intersectXPoint) + yInterseptLine1;
            //check to see if its on the line

            Point2D possibleIntersection = new Point2D(new Vector(intersectXPoint, intersectYPoint));

            //because of error, we make sure that the point is in the bounds of the line segments
            if (((((intersectXPoint <= x1) && (intersectXPoint >= x2)) || ((intersectXPoint >= x1) && (intersectXPoint <= x2))) &&
                    (((intersectYPoint <= y1) && (intersectYPoint >= y2)) || ((intersectYPoint >= y1) && (intersectYPoint <= y2)))) &&
                    ((((intersectXPoint <= x3) && (intersectXPoint >= x4)) || ((intersectXPoint >= x3) && (intersectXPoint <= x4))) &&
                    (((intersectYPoint <= y3) && (intersectYPoint >= y4)) || ((intersectYPoint >= y3) && (intersectYPoint <= y4))))) {
                return possibleIntersection;
            } else {
            }

        }
        // no interseciton
        return null;
    }

    /**
     * Computes the cross-sectional area of the LineSegment2D and Polygon instances given.
     * @param line an instance of LineSegment2D.
     * @param polygon an instance of Polygon.
     * @return the cross-sectional area of the LineSegment2D and Polygon instances given.
     */
    private static Component2D intersectLinePolygon(LineSegment2D line, Polygon shape) {

        if (contains(shape, line)) {
            return line;
        }

        // List of points of shape
        LinkedList<Point2D> shapePoints = shape.getListofPoints();
        LinkedList<Point2D> intersectionPoints = new LinkedList<Point2D>();
        Component2D intersection = null;
        // Loop through all edges of shape
        // start at 1 rather then 0
        int nextI = 0;
        for (int i = 0; i < shape.getListofPoints().size(); i++) {

            if (i + 1 == shape.getListofPoints().size()) {
                nextI = 0;
            } else {
                nextI = i + 1;
            }

            //Determine the intersection between the lines
            intersection = intersectLineLine(line, new LineSegment2D(shapePoints.get(i), shapePoints.get(nextI)));
            //If there was an intersection , check to see if it was a line or point.
            //If its a line then we know that it overlaps a line of the polygon
            //Since its convex, we know that it wont intersect again
            if (intersection instanceof LineSegment2D && intersection != null) {
                intersection = (LineSegment2D) intersection;
                return (LineSegment2D) intersection;
            } else if (intersection instanceof Point2D && intersection != null) {
                intersection = (Point2D) intersection;
                intersectionPoints.add((Point2D) intersection);
            }
        }
        //have to get rid of duplicates since intersection may pick up a point twice.
        if (intersectionPoints.size() > 1) {
            for (int j = 0; j < intersectionPoints.size() - 1; j++) {
                Point2D currentPoint = intersectionPoints.get(j);
                for (int k = j + 1; k < intersectionPoints.size();) {
                    if ((currentPoint.getX() == intersectionPoints.get(k).getX()) &&
                            (currentPoint.getY() == intersectionPoints.get(k).getY())) {
                        intersectionPoints.remove(k);
                    } else {
                        k++;
                    }
                }
            }
        }

        // Return the list of points
        // could be 0 , 1, or 2 points
        //We know that if we have 2 points, its a line
        //1 point would just be a point
        if (intersectionPoints.size() == 2) {
            if ((intersectionPoints.get(0).getX() == intersectionPoints.get(1).getX()) &&
                    (intersectionPoints.get(0).getY() == intersectionPoints.get(1).getY())) {
                return intersectionPoints.get(0);
            }
            return new LineSegment2D(intersectionPoints.get(0), intersectionPoints.get(1));
        } else if (intersectionPoints.size() == 1) {
            Point2D pointInside;
            if (containsPolygonPoint(shape, line.getListofPoints().get(0))) {
                pointInside = line.getListofPoints().get(0);
            } else if (containsPolygonPoint(shape, line.getListofPoints().get(1))) {
                pointInside = line.getListofPoints().get(1);
            } else {
                return intersectionPoints.get(0);
            }

            if (containsPointPoint(intersectionPoints.get(0), pointInside)) {
                return pointInside;
            } else {
                return new LineSegment2D(intersectionPoints.get(0), pointInside);
            }

        } else {
            return null;
        }

    }

    /**
     * Computes the cross-sectional area of the Point2D and LineSegment2D instances given.
     * @param point an instance of Point2D.
     * @param line an instance of LineSegment2D.
     * @return the cross-sectional area of the Point2D and LineSegment2D instances given.
     */
    private static Point2D intersectPointLine(Point2D point, LineSegment2D line1) {
        if ((line1.getListofPoints().size() == 0) || (point.getListofPoints().size() == 0)) {
            throw new IllegalArgumentException("No points in List");
        }

        // Call get list of points to be consistent
        double x3 = point.getListofPoints().getFirst().getX();
        double y3 = point.getListofPoints().getFirst().getY();
        boolean undefined = false;

        // Equations of a line
        // y = ax + b
        LinkedList<Point2D> line = line1.getListofPoints();
        double x2 = line.get(1).getX();
        double x1 = line.get(0).getX();
        double y2 = line.get(1).getY();
        double y1 = line.get(0).getY();

        // Slope of line
        if ((x2 - x1) == 0) {
            undefined = true;
        }

        //Is line undefined?
        if (undefined) {
            if ((x3 == x1) && ((y3 <= y2 && y3 >= y1) || (y3 >= y2 && y3 <= y1))) {
                return point;
            }

        } else {
            //Slope of the line
            double a = (y2 - y1) / (x2 - x1);
            // Y intercept
            double b = y1 - a * x1;

            // Check if point is on line ax + b
            // Make sure point is between endpoints of the line segment
            // We dont know which endpoint is between so check both
            // We make sure its on the line and that its in bounds.
            if ((y3 == (a * x3 + b)) && ((x3 <= x2 && x3 >= x1) || (x3 >= x2 && x3 <= x1))) {
                return point;
            }

        }
        return null;
    }

    /**
     * Computes the cross-sectional area of the two Point2D instances given.
     * @param point1 an instance of Point2D.
     * @param point2 an instance of Point2D.
     * @return the cross-sectional area of the two Point2D instances given.
     */
    private static Point2D intersectPointPoint(Point2D point1, Point2D point2) {
        //Just check that the points have the same x and y
        if (point1.getX() == point2.getX() && point1.getY() == point2.getY()) {
            return point1;
        }

        return null;
    }

    /**
     * Computes the cross-sectional area of the Point2D and Polygon instances given.
     * @param point an instance of Point2D.
     * @param polygon an instance of Polygon.
     * @return the cross-sectional area of the Point2D and Polygon instances given.
     */
    private static Point2D intersectPointPolygon(Point2D point, Polygon polygon) {
        LinkedList<Point2D> polyPoints = polygon.getListofPoints();
        Point2D intersection;

        boolean intersect = false;
        int nextI = 0;
        // Loop through all edges of polygon
        for (int i = 0; i < polyPoints.size() && !intersect; i++) {
            if (i + 1 == polyPoints.size()) {
                nextI = 0;
            } else {
                nextI = i + 1;
            }

            intersection = intersectPointLine(point, new LineSegment2D(polyPoints.get(i), polyPoints.get(nextI)));

            if (intersection != null) {
                intersect = true;
            }

        }
        // Final check if there was an intersection or if it is contained
        if (intersect || contains(polygon, point)) {
            return point;
        }

        // No intersection
        return null;
    }

    /**
     * Computes the cross-sectional area of the two Polygon instances given.
     * @param polygon1 an instance of Polygon.
     * @param polygon2 an instance of Polygon.
     * @return the cross-sectional area of the two Polygon instances given.
     * @throws IllegalArgumentException the two polygons provided do not intersect.
     */
    private static Component2D intersectPolygonPolygon(Polygon polygon1, Polygon polygon2) {
        if (contains(polygon1, polygon2)) {
            return polygon2;
        }
        if (contains(polygon2, polygon1)) {
            return polygon1;
        }

        LinkedList<Point2D> intersectingShape = new LinkedList<Point2D>();

        // Determine if the any points in poly 1 exist in poly 2, if so add them to the new shape
        for (Point2D point : polygon1.getListofPoints()) {
            if (contains(polygon2, point)) {
                intersectingShape.add(point);
            }
        }

        // Determine if the any points in poly 2 exist in poly 1, if so add them to the new shape
        for (Point2D point : polygon2.getListofPoints()) {
            if (contains(polygon1, point)) {
                intersectingShape.add(point);
            }
        }

        int j = 0;

        LinkedList<LineSegment2D> poly1Edges = new LinkedList<LineSegment2D>();
        LinkedList<LineSegment2D> poly2Edges = new LinkedList<LineSegment2D>();

        // Generate all edges for poly 1 for intersection checks
        for (int i = 0; i < polygon1.getListofPoints().size(); i++) {
            if (j + 1 == polygon1.getListofPoints().size()) {
                j = 0;
            } else {
                j++;
            }

            poly1Edges.add(new LineSegment2D(polygon1.getListofPoints().get(i), polygon1.getListofPoints().get(j)));
        }

        // Generate all edges for poly 2 for intersection checks
        for (int i = 0; i < polygon2.getListofPoints().size(); i++) {
            if (j + 1 == polygon2.getListofPoints().size()) {
                j = 0;
            } else {
                j++;
            }

            poly2Edges.add(new LineSegment2D(polygon2.getListofPoints().get(i), polygon2.getListofPoints().get(j)));
        }

        // If any edge intersections occur, add the point of intersection to the new shape
        for (int k = 0; k < poly1Edges.size(); k++) {
            for (int h = 0; h < poly2Edges.size(); h++) {
                Component2D intersection = intersect(poly1Edges.get(k), poly2Edges.get(h));

                if (intersection != null && intersection instanceof Point2D) {
                    intersectingShape.add((Point2D) intersection);
                }
            }
        }

        if (intersectingShape.size() == 0) {
            throw new IllegalArgumentException("The two polygons provided do not intersect.");
        }

        // Get the center point of the proposed shape. This center point will
        // provide us the displacement required to shift the points to so they
        // revolve around the origin.
        Rectangle bounding = Polygon.getBoundingBox(intersectingShape);
        Vector location = bounding.getLocation();

        boolean xAdd = location.getX() < 0;
        boolean yAdd = location.getY() < 0;

        LinkedList<Double> polarTheta = new LinkedList<Double>();

        // The list of points for the new shape is done, but the points are likely
        // out of order. All points are coverted to polar coordinates first. Then the
        // angle is calculated for each polar coordinate from 0 to 2PI.
        for (Point2D pt : intersectingShape) {
            double x, y;

            // Shift the point towards to origin (0,0) based on the bounding box center
            if (xAdd) {
                x = pt.getX() + Math.abs(location.getX());
            } else {
                x = pt.getX() - location.getX();
            }

            if (yAdd) {
                y = pt.getY() + Math.abs(location.getY());
            } else {
                y = pt.getY() - location.getY();
            }

            double r = distance(new Point2D(new Vector(x, y)), new Point2D(new Vector(0, 0)));
            double theta = Math.toDegrees(Math.atan2(y, x));

            polarTheta.add(new Double(theta));
        }

        LinkedList<Point2D> orderedShape = new LinkedList<Point2D>();

        // The angles are then sorted in decreasing order, which makes the list
        // of points for the new shape clockwise.
        while (!intersectingShape.isEmpty()) {
            double highest = Double.NEGATIVE_INFINITY;
            Point2D currentPoint = intersectingShape.get(0);
            int index = 0;
            for (int i = 0; i < intersectingShape.size(); i++) {


                if (polarTheta.get(i) > highest) {
                    highest = polarTheta.get(i);
                    currentPoint = intersectingShape.get(i);
                    index = i;
                }
            }

            orderedShape.add(currentPoint);
            intersectingShape.remove(index);
            polarTheta.remove(index);
        }

        return new IrregularConvexPolygon(orderedShape);
    }
}
